import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-23
 * Time: 22:57
 */
public class Solution {
//     dp
//     dp[j][k]表示 以arr[j], arr[k]作为最后两个数字的斐波那契数列的最大长度
//     dp[j][k]=dp[i][j]+(存在arr[i]使得 arr[i]+arr[j]=arr[k])与3两个数中较大的那个
//     同时需要防止 得到的 下标 i >= j, 所以 arr[j]*2 > arr[k]
//     因为出现斐波那契数列, 数字个数最少为 3 个
    public int lenLongestFibSubseq(int[] arr) {
        int max=0;
        int length=arr.length;
        int[][] dp=new int[length][length];
        // 使用map 方便判断是否存在 前一个数
        Map<Integer, Integer> map=new HashMap<>();
        for(int i=0;i<length;i++){
            map.put(arr[i], i);
        }

        // k 为第三个数下标, j 为第二个,  i 为第一个
        for(int k=0;k<length;k++){
            // 因为 j 为第二个, 所以当然 j 要倒着来
            // 同时因为 i 为 第一个, 所以 arr[k]-arr[j] 得到的下标必须<j
            // 也就是 arr[j]*2>arr[k]
            for(int j=k-1;j>=0&&arr[j]*2>arr[k];j--){
                int i=map.getOrDefault(arr[k]-arr[j], -1);
                if(i>=0){
                    // 一旦出现 满足条件的斐波那契数列那么 数字的个数最少为 3 个
                    dp[j][k]=Math.max(dp[i][j]+1, 3);
                    max=Math.max(max, dp[j][k]);
                }
            }
        }
        return max;
    }
}